package com.sicheng.lc.周赛.分类.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/16 15:53
 */
public class 字符串总引力 {
    //    https://leetcode.cn/problems/total-appeal-of-a-string/
    // todo 待优化  需要O(nlogn)
    public long appealSum(String s) {
        long[] dp = new long[s.length()];
        dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            int state = 0;
            dp[i] += dp[i - 1];
            int count = 0;
            for (int j = i; j >= 0; j--) {
                int x = 1 << s.charAt(j) - 'a';
                if ((x & state) == 0) {
                    count++;
                    state |= x;
                }
                dp[i] += count;
            }
        }
        return dp[s.length() - 1];
    }
}
